#include<string>
using std::string;


struct PreTreeNode
{
    PreTreeNode* next[26];
    bool hasStop;
    PreTreeNode() {
        for (int i = 0; i < 26; i++) {
            next[i] = nullptr;
        }
        hasStop = false;
    }
};

class Trie {
public:

    Trie() {
    }
    
    void insert(string word) {
        PreTreeNode* cur = &root;
        for (auto& c: word) {
            int idx = c - 'a';
            if (!cur->next[idx])
                cur->next[idx] = new PreTreeNode();
            cur = cur->next[idx];
        }
        cur->hasStop = true;
    }
    
    bool search(string word) {
        PreTreeNode* cur = &root;
        for (auto& c: word) {
            int idx = c - 'a';
            if (cur->next[idx]) cur = cur->next[idx];
            else return false;
        }
        if (cur->hasStop) return true;
        return false;
    }
    
    bool startsWith(string prefix) {
        PreTreeNode* cur = &root;
        for (auto& c: prefix) {
            int idx = c - 'a';
            if (cur->next[idx]) cur = cur->next[idx];
            else return false;
        }
        return true;
    }


private:
    PreTreeNode root;
};

/**
 * Your Trie object will be instantiated and called as such:
 * Trie* obj = new Trie();
 * obj->insert(word);
 * bool param_2 = obj->search(word);
 * bool param_3 = obj->startsWith(prefix);
 */